package leetcode.code0851;

import java.util.ArrayList;
import java.util.List;

public class Solution extends S851 {

	public class Info {

		int me;
		List<Integer> richers;

		public Info(int me) {
			richers = new ArrayList<>();
			this.me = me;
		}

	}

	@Override
	public int[] loudAndRich(int[][] richer, int[] quiet) {
		int n = quiet.length;
		Info[] infos = new Info[n];
		for (int i = 0; i < n; i++) {
			infos[i] = new Info(i);
		}
		for (int[] element : richer) {
			int a = element[0];
			int b = element[1];
			infos[b].richers.add(a);
		}
		int[] ans = new int[n];
		int[] seen = new int[n];
		for (int i = 0; i < n; i++) {
			this.f(i, ans, seen, quiet, infos);
		}
		return ans;
	}

	private void f(int i, int[] ans, int[] seen, int[] quiet, Info[] infos) {
		if (seen[i] == 1) {
			return;
		}
		seen[i] = 1;
		ans[i] = i;
		for (int richer : infos[i].richers) {
			this.f(richer, ans, seen, quiet, infos);
			if (quiet[ans[richer]] < quiet[ans[i]]) {
				ans[i] = ans[richer];
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
